package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <a href="https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/description/">两数之和 IV - 输入二叉搜索树(Two Sum IV - Input is a BST)</a>
 * <p>给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。</p>
 * <pre>
 * 示例 1：
 *      输入: root = [5,3,6,2,4,null,7], k = 9
 *                      5
 *                    /   \
 *                   3     6
 *                  / \     \
 *                 2   4     7
 *      输出: true
 *
 * 示例 2：
 *      输入: root = [5,3,6,2,4,null,7], k = 28
 *                      5
 *                    /   \
 *                   3     6
 *                  / \     \
 *                 2   4     7
 *      输出: false
 * </pre>
 * <b>提示:</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是  [1, 10^4].</li>
 *     <li>-10^4 <= Node.val <= 10^4</li>
 *     <li>题目数据保证，输入的 root 是一棵 有效 的二叉搜索树</li>
 *     <li>-10^5 <= k <= 10^5</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/23 17:44
 */
public class LC0653FindTarget_S {

    public boolean findTarget(TreeNode root, int k) {
        if (root.left == null && root.right == null) {
            return false;
        }
        //List<Integer> valList = new ArrayList<>();
        //findTargetByRecursion(root, valList);
        List<Integer> valList = findTargetByIteration(root);
        int leftIndex = 0;
        int rightIndex = valList.size() - 1;
        while (leftIndex < rightIndex) {
            if (valList.get(leftIndex) + valList.get(rightIndex) > k) {
                --rightIndex;
            } else if (valList.get(leftIndex) + valList.get(rightIndex) < k) {
                ++leftIndex;
            } else {
                return true;
            }
        }
        return false;
    }

    public List<Integer> findTargetByIteration(TreeNode node) {
        List<Integer> valList = new ArrayList<>();
        if (node == null) {
            return valList;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            valList.add(node.val);
            node = node.right;
        }
        return valList;
    }

    public void findTargetByRecursion(TreeNode node, List<Integer> valList) {
        if (node == null) {
            return;
        }
        findTargetByRecursion(node.left, valList);
        valList.add(node.val);
        findTargetByRecursion(node.right, valList);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(7);
        LC0653FindTarget_S lc0653FindTarget_s = new LC0653FindTarget_S();
        System.out.println(lc0653FindTarget_s.findTarget(root, 9));
    }
}
